package heap.shiftUp;

/**
 * 插入新的元素，执行shiftUp操作，保持二叉堆的性质
 * mxf
 * 2018年5月28日17:30:20
 * @param <Item>
 */
public class MaxHeap<Item extends Comparable> {

    protected Item[] data; // 数组
    protected int count; // 元素的个数
    protected int capacity; // 数组的长度

    // 构造函数, 构造一个空堆, 可容纳capacity个元素
    public MaxHeap(int capacity){
        this.data = (Item[])new Comparable[capacity+1];
        this.count = 0;
        this.capacity = capacity;
    }

    // 返回堆中的元素个数
    public int size(){
        return count;
    }

    // 返回一个布尔值, 表示堆中是否为空
    public boolean isEmpty(){
        return count == 0;
    }

    public void insert(Item item) {
        assert count + 1 <= capacity;
        count++;
        data[count] = item;
        shiftUp(count);
    }

    //********************
    //* 最大堆核心辅助函数
    //********************
    private void shiftUp(int k) {
        while (k > 1 && data[k].compareTo(data[k / 2]) > 0) {
            swap(k, k / 2);
            k = k / 2;
        }
    }

    // 交换堆中索引为i和j的两个元素
    private void swap(int i, int j){
        Item t = data[i];
        data[i] = data[j];
        data[j] = t;
    }

    // 测试 MaxHeap
    public static void main(String[] args) {

        MaxHeap<Integer> maxHeap = new MaxHeap<Integer>(100);
        int N = 50; // 堆中元素个数
        int M = 100; // 堆中元素取值范围[0, M)
        for( int i = 0 ; i < N ; i ++ )
            maxHeap.insert( new Integer((int)(Math.random() * M)) );
        System.out.println(maxHeap.size());

    }
}
